package springframework.test;


import java.util.ArrayList;
import java.util.Arrays;

public class RadixSortA {


    public static void main(String[] args) {
        String[] strings = {"rfsd", "gghd", "what", "your", "mean", "java"};
//        RadixSort.countingRadixSort(strings, 4);
        radixSortCounting(strings, 4);
        Arrays.stream(strings).forEach(System.out::println);


//        int[] strings = {34, 232, 4, 5, 23, 5090, 656, 7, 787, 878, 2323};
//        radixSortB(strings, 4);
//        Arrays.stream(strings).forEach(System.out::println);
    }


    public static void radixSortA(String[] args, int stringLen) {
        final int BUCKETS = 256;
        ArrayList<String>[] buckets = new ArrayList[BUCKETS];
        for (int i = 0; i < BUCKETS; i++) {
            buckets[i] = new ArrayList<>();
        }
        for (int pos = stringLen - 1; pos >= 0; pos--) {
            for (String s : args) {
                buckets[s.charAt(pos)].add(s);
            }
            int idx = 0;
            for (ArrayList<String> bucket : buckets) {
                for (String s : bucket) {
                    args[idx++] = s;
                }
                bucket.clear();
            }
            Arrays.stream(args).forEach(System.out::println);
            System.out.println("-----------------------------------------------");
        }

    }


    static final int[] diag = {1, 10, 100, 1000};

    private static int getRadixDaital(int x, int d) {
        return x / diag[d] % 10;
    }


    /***
     *
     * @param args
     * @param numLen
     */
    public static void radixSortB(int[] args, int numLen) {
        ArrayList<Integer>[] buckets = new ArrayList[10];
        //构建桶
        for (int i = 0; i < 10; i++) {
            buckets[i] = new ArrayList<>();
        }
        //分割数字位数
        for (int i = 0; i < numLen; i++) {
            for (int arg : args) {
                int daital = getRadixDaital(arg, i);
                ArrayList<Integer> bucket = buckets[daital];
                bucket.add(arg);
            }
            int idx = 0;
            for (ArrayList<Integer> bucket : buckets) {
                for (Integer s : bucket) {
                    args[idx++] = s;
                }
                bucket.clear();
            }
            Arrays.stream(args).forEach(System.out::println);
            System.out.println("-----------------------------------------------");
        }
    }

    public static void radixSortCounting(String[] args, int strLength) {
        final int buckets = 256;
        int N = args.length;
        String[] in = args;
        String[] buffer = new String[N];
        String[] out = buffer;
        for (int pos = strLength - 1; pos >= 0; pos--) {
            //计数器
            int[] count = new int[buckets + 1];
            //初始化桶的位置
            for (int i1 = 0; i1 < N; i1++) {
                count[in[i1].charAt(pos)]++;
            }
            //对桶进行计数
            for (int i1 = 1; i1 <= buckets; i1++) {
                count[i1] += count[i1 - 1];
            }
            //
            for (int i1 = 0; i1 < N; i1++) {
                out[count[in[i1].charAt(pos)]++] = in[i1];
            }

            //   for (int i = 0; i < N; i++)
            //                count[in[i].charAt(pos) + 1]++;
            //
            //            for (int b = 1; b <= BUCKETS; b++)
            //                count[b] += count[b - 1];
            //
            //            for (int i = 0; i < N; i++)
            //                out[count[in[i].charAt(pos)]++] = in[i];
            //
            String[] tmp = in;
            in = out;
            out = tmp;

        }
        if (strLength % 2 == 1) {
            for (int i = 0; i < N; i++) {
                out[i] = in[i];
            }
        }
    }

}
